When an electronic system includes multiple cache memories, the validity of the data available for use must be maintained. This is typically accomplished by manipulating data according to a cache coherency protocol. As the number of caches and/or processors increases, the complexity of maintaining cache coherency also increases.
When multiple components (e.g., a cache memory, a processor) request the same block of data the conflict between the multiple components must be resolved in a manner that maintains the validity of the data. Current cache coherency protocols typically have a single component that is responsible for conflict resolution. However, as the complexity of the system increases, reliance on a single component for conflict resolution can decrease overall system performance.
FIGS. 1a through 1e provide a conceptual illustration of a conflict condition in a multi-node system. Nodes 110, 120 and 130 are peer nodes that can store a copy of the requested data (e.g., a cache line) in cache memory. Home node 140 is the Home (H) node for the requested data. In the example of FIGS. 1a through 1e, peer nodes 110 and 120 store an invalid copy, or no copy, of the requested data and peer node 130 stores a modified copy of the requested data that has not been written back to memory. The Home node stores the original copy of the data in memory or modified versions of the data when the modifications are written back to memory.
As illustrated in FIG. 1a, peer node 120 transmits a Data Request message to request a copy of a block of data, for example, a cache line. The Data Request message is transmitted to peer node 110 and to peer node 130. However, the Data Request message to peer node 130 is delayed. The delay can be caused, for example, by lack of available bandwidth, buffering considerations, etc.
Peer node 110 responds to the Data Request message from peer node 120 with a No Valid Copy message, which indicates to peer node 120 that peer node 110 does not have a valid copy of the requested data. At some time after peer node 120 transmits Data Request messages, Peer node 110 transmits Data Request messages to peer nodes 120 and 130, as illustrated in FIG. 1b, requesting the same data as was requested by peer node 120.
Peer node 120 provides a No Valid Copy message to peer node 110 in response to the Data Request message. Peer node 130 provides the requested data to peer node 110. The copy of the data, if any, maintained by peer node 130 is marked invalid and the copy of the data stored by peer node 110 is marked Modified.
At some time after peer node 130 has responded to the Data Request from peer node 110 and invalidated the copy of the data, peer node 130 receives the delayed Data Request message from peer node 120, as illustrated in FIG. 1c. In response to the Data Request message, peer node 130 provides a No Valid Copy message to peer node 120. Note that the state of the data stored by peer node 130 changed from the time of the original Data Request message to the time the peer node 130 responds to the Data Request message.
Because peer nodes 110 and 130 respond to the Data Request message from peer node 120 with No Valid Copy messages, peer node 120, finding no valid cached copy of the requested data, requests a copy of the data from home node 140. Thus, as illustrated in FIG. 1d, peer node transmits a Read message to home node 140. Home node 140 retrieves the requested data from memory and provides the data to peer node 120. Peer node 120 then stores the requested data in the Exclusive state.
As illustrated in FIG. 1e, the sequence of messages illustrated in FIGS. 1a through 1e result in two incompatible copies of a data line. In the example provided peer node 110 stores a copy of the data in the Modified state and peer node 120 stores a copy of the data in the Exclusive state. However, the copy stored by peer node 120 is not exclusive to peer node 120. Thus, multi-node systems can result in incompatible copies of data under certain circumstances unless a mechanism is provided to resolve cache conflicts.